#include<vector>
#include<iostream>

using namespace std;
vector<int> insertionSortRecursive(vector<int> array, int nextPos) {
  if (nextPos == array.size()){
    return array;
  }
  int i = nextPos;
  while (i > 0 && array[i] < array[i - 1]) {
    swap(array[i], array[i - 1]);
    i--;
  }
  return insertionSortRecursive(array, nextPos + 1);
}
vector<int> insertionSort(vector<int> array) {
  for (int i = 0; i < array.size(); i++) {
    int j = i;
    while (j > 0 && array[j] < array[j - 1]) {
        swap(array[j], array[j - 1]);
        j--;
    }
  }
  return array;
}

int main(int argc, char const *argv[]) {
  vector<int> array {1, 4, 2, 6, 8, 9, -2};
  for (int i : insertionSort(array)) {
    cout << i << " ";
  }
  return 0;
}
